/*
 * tabbporo.h
 *
 *  Created on: 03/02/2010
 *      Author: javier
 */

#ifndef TABBPORO_H_
#define TABBPORO_H_

#include <iostream>
#include "tporo.h"
#include "tvectorporo.h"
#include "tcolaabbporo.h"

using namespace std;

/** \file tabbporo.h
 *  \brief Implementación del tipo Arbol binario de tporos, mediante las clases TNodoABB y TABBPoro.
 *
 * Este fichero contiene la estructura de la clase Arbol binario de tporos y la clase auxiliar a esta Nodos del arbol binario de poros.
 */



class TColaABBPoro;
class TNodoABB;

/** \brief Estructura de TABBPoro.
 *
 *  En esta clase encontramos las funciones para el arbol binario, y su especificación.
 */
class TABBPoro
{

	friend class TNodoABB;
	friend class TECAP;
	friend class TColaABBPoro;

	/** \brief Sobrecarga del operador "<<", función amiga de TABBPoro.
	 *
	 * Función amiga que se encarga de mostrar por pantalla, en formato como el del vector el recorrido por niveles del arbol.
	 *
	 * \param os Ostream donde guardaremos la informacion que queremos mostrar.
	 * \param arb Arbol que mostraremos.
	 *
	 * \return La funcion devuelve un ostream&.
	 */
	friend ostream & operator<<( ostream &, const TABBPoro &);

	public:

		/** \brief Constructor de la clase.
		 *
		 * Constructor de la clase por defecto, donde creamos un nodo por defecto.
		 */
		TABBPoro();

		/** \brief Constructor de copia.
		 *
		 * Constructor de copia de la clase TABBPoro.
		 * \param n Arbol desde el que copiamos.
		 */
		TABBPoro(const TABBPoro &);

		 /** Destructor.
		 *
		 * Destructor de la clase TABBPoro.
		 */
		~TABBPoro();

		 /** \brief Sobrecarga del operador asignación.
		 *
		 * En esta sobrecarga asignamos el contenido del argumento al TABBPoro que llame al método.
		 * Si el Arbol que llama a la función tenía contenido se borra y asignamos el parámetro.
		 *
		 * \param p TABBPoro a partir del cual asignamos.
		 * \return TABBPoro& es devuelto con la correspondiente asignación efectuada.
		 */
		TABBPoro & operator=( const TABBPoro & );

		/** \brief Sobrecarga del operador igualdad.
		 *
		 * Comparamos en primer lugar si las alturas de los árboles son iguales, para si es así comprobar sus recorridos inorden.
		 * Que deben dar igual.
		 * \param p Otro arbol, con el que compararemos.
		 * \return Devuelve un bool, que indica si es igual o si no lo es.
		 */
		bool operator==( const TABBPoro & );

        /** \brief Metodo EsVacio().
         *
         * Devuelve true si el arbol esta vacio y false si no lo está.
         * La condicion de que este vacio es el primer nodo apuntando a NULL.
         *
         * \return  Devuelve un bool para indicar su estado.
         */
		bool EsVacio() const;


		/** \brief Operador Insertar.
		 *
		 * Este operador se encarga de la inserción ordenada en el árbol b. de poros.
		 * Mediante un proceso recursivo vamos analizando las ramas del árbol, de forma que recorreremos en orden
		 * hasta encontrar un hueco donde meterlo. En el caso de que haya un nodo de igual volumen no se inserta.
		 *
		 * \param p Un TPoro, el que vamos a insertar.
		 * \return Devuelve un bool, que indica si se ha insertado o no se ha insertado.
		 */
		bool Insertar( TPoro &);

		/** \brief Operador Borrar.
		 *
		 * Borrar busca el elemento que le hemos pasado al método en el arbol, y si lo encuentra lo elimina
		 * efectuando sus correspondientes opereciones de reestructuración del arbol. Para ello cuenta con una funcion
		 * auxiliar (IntercambiarBorrar).
		 *
		 * \param p TPoro a borrar en el árbol
		 * \return Devuelve un bool, que indica si se ha borrado o no se ha borrado, si no se borra no estaba en el arbol.
		 */
		bool Borrar( const TPoro &);

		/** \brief Operador Buscar.
		 *
		 * Este operador se encarga de buscar el poro que le pasamos por argumento en el arbol e indicarnoslo mediante un bool.
		 *
		 * \param p TPoro a buscar en el árbol
		 * \return Devuelve un bool, que indica si se ha encontrado, true si, false no.
		 */
		bool Buscar( const TPoro &) const;

		/** \brief Operador Raiz.
		 *
		 * Raiz nos devuelve el TPoro que se encuentra en la raiz del arbol.
		 *
		 * \return Devuelve un TPoro, el correspondiente a la raiz del arbol.
		 */
		TPoro Raiz() const;

		/** \brief Operador Altura.
		 *
		 * Altura, calcula la altura del arbol y nos la devuelve como entero.
		 *
		 * \return Devuelve un entero con el valor de la altura.
		 */
		int Altura() const;

		/** \brief Operador Nodos.
		 *
		 * Este operador calcula el numero de nodos en el arbol.
		 *
		 * \return Devuelve un entero con el numero de nodos.
		 */
		int Nodos() const;

		/** \brief Operador NodosHoja.
		 *
		 * Este operador calcula el numero de nodos hoja en el arbol.
		 *
		 * \return Devuelve un entero con el numero de nodos hoja.
		 */
		int NodosHoja();

		/** \brief Operador +.
		 *
		 * El operador suma saca un ABB nuevo con los elementos del arbol de la izquierda y los de la derecha insertados por niveles.
		 *
		 * \param p Arbol operando derecho.
		 * \return Devuelve TABBPoro con el contenido descrito.
		 */
		TABBPoro operator+( const TABBPoro &);

		/** \brief Operador -.
		 *
		 * El operador suma saca un ABB nuevo con los elementos del arbol de la izquierda que no esten en el de la derecha.
		 *
		 * \param p Arbol operando derecho.
		 * \return Devuelve TABBPoro con el contenido descrito.
		 */
		TABBPoro operator-( const TABBPoro &);

		/** \brief Operador Inorden.
		 *
		 * Inorden nos devuelve el recorrido Inorden del arbol.
		 *
		 * \return Devuelve un TVectorPoro con el contenido del recorrido Inorden.
		 */
		TVectorPoro Inorden() const;

		/** \brief Operador Preorden.
		 *
		 * Preorden nos devuelve el recorrido Preorden del arbol binario.
		 *
		 * \return Devuelve un TVectorPoro con el contenido del recorrido.
		 */
		TVectorPoro Preorden() const;

		/** \brief Operador Postorden.
		 *
		 * Postorden nos devuelve el recorrido Postorden del arbol binario.
		 *
		 * \return Devuelve un TVectorPoro con el contenido del recorrido.
		 */
		TVectorPoro Postorden() const;

		/** \brief Operador Niveles
		 *
		 * Niveles nos devuelve el recorrido del arbol binario por niveles.
		 *
		 * \return Devuelve un TVectorPoro con el contenido del recorrido.
		 */
		TVectorPoro Niveles() const;


		friend ostream & operator<<(ostream &, const TColaABBPoro &);

	private:

        /** \brief puntero a TNodoABB
         *
         * Puntero a un objeto TNodoABB, que conforman la estructura interna del arbol binario.
         */
		TNodoABB *nodo;

		//void EliminarABB( TNodoABB &n );

		/** \brief IntercambiarBorrar.
		 *
		 * Esta funcion auxiliar de Borrar, se encarga de la busqueda del elemento menor de la izquierda del las ramas del arbol
		 * para sustituirlo por el elemento a borrar.
		 *
		 * \return Void no devuelve nada.
		 */
		void IntercambiarBorrar();

		/** \brief InordenAux.
		 *
		 * Funcion auxiliar de del metodo Inorden(). Mediante un proceso recursivo obtenemos el recorrido Inorden.
		 *
		 * \param v Vector donde guardamos el recorrido.
		 * \param i posicion a examinar para el guardado.
		 * \return Void no devuelve nada.
		 */
		void InordenAux( TVectorPoro &, int &) const;

		/** \brief PreordenAux.
		 *
		 * Funcion auxiliar de del metodo Preorden(). Mediante un proceso recursivo obtenemos el recorrido Inorden.
		 *
		 * \param v Vector donde guardamos el recorrido.
		 * \param i posicion a examinar para el guardado.
		 * \return Void no devuelve nada.
		 */
		void PreordenAux( TVectorPoro &, int &) const;

		/** \brief PostordenAux.
		 *
		 * Funcion auxiliar de del metodo Postorden(). Mediante un proceso recursivo obtenemos el recorrido Inorden.
		 *
		 * \param v Vector donde guardamos el recorrido.
		 * \param i posicion a examinar para el guardado.
		 * \return Void no devuelve nada.
		 */
		void PostordenAux( TVectorPoro &, int &) const;

		/** \brief BuscarpaRestar.
		 *
		 * Funcion auxiliar del operador resta.
		 *
		 * \param p poro a buscar.
		 * \return bool devuelve true si lo ha encontrado.
		 */
		bool BuscarpaRestar(const TPoro &p );

		//bool CompararABB( const TNodoABB &a, const TNodoABB &b);
};


/** \brief Estructura de TNodoABB.
 *
 *  En esta clase encontramos los metodos de la clase TNodoABB que conforma la estructura interna del TABBPoro.
 */
class TNodoABB
{
	friend class TECAP;
	friend class TColaABBPoro;
	friend class TABBPoro;

	public:

		/** \brief Constructor de la clase.
		 *
		 * Constructor de la clase por defecto.
		 */
		TNodoABB();

        /** \brief Constructor de copia.
         *
         * Constructor de copia.
         * \param n TNodoABB desde el que se copia.
         */
		TNodoABB( const TNodoABB & );

        /** \brief Destructor.
         *
         * Destructor de la clase.
         */
		~TNodoABB();

        /** \brief Sobrecarga del operador asignación.
         *
         * En esta sobrecarga asignamos el contenido del argumento al TNodoABB que llama al metodo.
         * \param n TNodo ABB del que copiamos.
         * \return TNodoABB &.
         */
		TNodoABB & operator=( const TNodoABB &);


		friend ostream & operator<<(ostream &, const TColaABBPoro &);

	private:

		//void Copiar( const TNodoABB &n );

		/** \brief Eliminar().
		 *
		 * Funcion auxiliar del destructor de Nodo, se encarga de recorrer el arbol y borrar el contenido de memoria.
		 *
		 * \return Void no devuelve nada.
		 */
		void Eliminar( TNodoABB &n );

        /** \brief item
         *
         * Elemento que contiene el nodo tipo TPoro.
         */
		TPoro item;

        /** \brief iz
         *
         * TABBPoro que conforma el hijo izquierdo del nodo.
         */
		TABBPoro iz;

        /** \brief iz
         *
         * TABBPoro que conforma el hijo derecho del nodo.
         */
		TABBPoro de;
};




#endif /* TABBPORO_H_ */
